package com.dyz.swordFingerOffer;

import java.util.ArrayList;
import java.util.List;


/**
 * @author: daiyizheng
 * @date: 2021/5/27 21:51
 * @description:
 */
//递归
public class Fibonacci10 {
    public int Fibonacci(int n){
        //n=0 时 返回 0
        // n=1 时 返回 1
        // 递归 f(n) = f(n-1)+f(n-2)
        if (n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        if (n>1){
            return Fibonacci(n-1)+Fibonacci(n-2);
        }

        return 0;
    }

    public int Fibonacci1(int n){
        //n=0 时 返回 0
        // n=1 时 返回 1
        // 递归 f(n) = f(n-1)+f(n-2)
        if(n<0){
            return 0;
        }
        if (n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(0);
        arrayList.add(1);
        for (int i = 2; i<=n; i++){
            arrayList.add(i, arrayList.get(i-1)+arrayList.get(i-2));
        }

        return arrayList.get(n);
    }

    public static void main(String[] args) {
        Fibonacci10 fibonacci10 = new Fibonacci10();
        System.out.println(fibonacci10.Fibonacci1(4));
    }
}
